{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Kth Bit in Nth Binary String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findKthBit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出第 N 个二进制字符串中的第 K 位"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个正整数 <code>n</code> 和 <code>k</code>，二进制字符串  <code>S<sub>n</sub></code> 的形成规则如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>S<sub>1</sub> = \"0\"</code></li>\n",
    "\t<li>当 <code>i > 1</code> 时，<code>S<sub>i</sub> = S<sub>i-1</sub> + \"1\" + reverse(invert(S<sub>i-1</sub>))</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>其中 <code>+</code> 表示串联操作，<code>reverse(x)</code> 返回反转 <code>x</code> 后得到的字符串，而 <code>invert(x)</code> 则会翻转 x 中的每一位（0 变为 1，而 1 变为 0）。</p>\n",
    "\n",
    "<p>例如，符合上述描述的序列的前 4 个字符串依次是：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>S<sub>1 </sub>= \"0\"</code></li>\n",
    "\t<li><code>S<sub>2 </sub>= \"0<strong>1</strong>1\"</code></li>\n",
    "\t<li><code>S<sub>3 </sub>= \"011<strong>1</strong>001\"</code></li>\n",
    "\t<li><code>S<sub>4</sub> = \"0111001<strong>1</strong>0110001\"</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回  <code>S<sub>n</sub></code> 的 <strong>第 <code>k</code> 位字符</strong> ，题目数据保证 <code>k</code> 一定在 <code>S<sub>n</sub></code> 长度范围以内。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, k = 1\n",
    "<strong>输出：</strong>\"0\"\n",
    "<strong>解释：</strong>S<sub>3</sub> 为 \"<strong>0</strong>111001\"，其第 1 位为 \"0\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, k = 11\n",
    "<strong>输出：</strong>\"1\"\n",
    "<strong>解释：</strong>S<sub>4</sub> 为 \"0111001101<strong>1</strong>0001\"，其第 11 位为 \"1\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1, k = 1\n",
    "<strong>输出：</strong>\"0\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, k = 3\n",
    "<strong>输出：</strong>\"1\"\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n <= 20</code></li>\n",
    "\t<li><code>1 <= k <= 2<sup>n</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-kth-bit-in-nth-binary-string](https://leetcode.cn/problems/find-kth-bit-in-nth-binary-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-kth-bit-in-nth-binary-string](https://leetcode.cn/problems/find-kth-bit-in-nth-binary-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n1', '4\\n11']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        if k == 1:\n",
    "            return \"0\"\n",
    "        \n",
    "        mid = 1 << (n - 1)\n",
    "        if k == mid:\n",
    "            return \"1\"\n",
    "        elif k < mid:\n",
    "            return self.findKthBit(n - 1, k)\n",
    "        else:\n",
    "            k = mid * 2 - k\n",
    "            return str(1 - int(self.findKthBit(n - 1, k)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invert(self,s):\n",
    "        return \"1\" if s==\"0\" else \"0\"\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        \n",
    "        if n==1:return \"0\"\n",
    "        if k==2**(n-1):return \"1\"\n",
    "        if k>2**(n-1):\n",
    "            return self.invert(self.findKthBit(n-1,2**(n-1)-k%(2**(n-1))))\n",
    "        else:\n",
    "            return self.findKthBit(n-1,k)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        if k == 1:\n",
    "            return \"0\"\n",
    "        n -= 1\n",
    "        mid = 1 << (n)\n",
    "        if k == mid:\n",
    "            return \"1\"\n",
    "        elif k < mid:\n",
    "            return self.findKthBit(n, k)\n",
    "        else:\n",
    "            k = (mid << 1) - k\n",
    "            return str(1 - int(self.findKthBit(n, k)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        if n == 1:\n",
    "            return '0'\n",
    "        # ln = 2 ** n - 1\n",
    "        mid = 2 ** (n - 1)\n",
    "        if mid == k:\n",
    "            return '1'\n",
    "        elif mid < k:\n",
    "            tmp = self.findKthBit(n - 1, 2 ** n - k)\n",
    "            return str(1 - int(tmp))\n",
    "        return self.findKthBit(n - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        if k==1:\n",
    "            return \"0\"\n",
    "        if k==2**(n-1):\n",
    "            return \"1\"\n",
    "        elif k<2**(n-1):\n",
    "            return self.findKthBit(n-1,k)\n",
    "        else:\n",
    "            if self.findKthBit(n-1,2**n-k)==\"1\":\n",
    "                return \"0\"\n",
    "            else:\n",
    "                return \"1\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        if k == 1:\n",
    "            return '0'\n",
    "        \n",
    "        mid = 1 << (n - 1)\n",
    "        if k == mid:\n",
    "            return \"1\"\n",
    "        elif k < mid:\n",
    "            return self.findKthBit(n - 1, k)\n",
    "        else:\n",
    "            k = mid * 2 - k\n",
    "            return \"0\" if self.findKthBit(n - 1, k) == \"1\" else \"1\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "                    \n",
    "            \n",
    "                    def Len(n):\n",
    "                        if n == 1:return 1\n",
    "                        return 2 * Len(n-1) + 1\n",
    "                    def dfs(n,k):\n",
    "                        if n == 1:return 0\n",
    "                        L = Len(n)\n",
    "                        if k == L // 2 + 1:\n",
    "                            return 1\n",
    "                        if k <= L // 2:\n",
    "                            return dfs(n - 1,k)\n",
    "                        return dfs(n-1,L - k + 1) ^ 1\n",
    "                    \n",
    "                    return str(dfs(n,k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        def dp(n, k, flag):\n",
    "            if(n == 1):\n",
    "                return 0^flag\n",
    "            m = n >> 1\n",
    "            if(k-1 == m):\n",
    "                return 1^flag\n",
    "            elif(k-1 < m):\n",
    "                return dp(m,k,flag)\n",
    "            else:\n",
    "                return dp(m,n-k+1,flag^1)\n",
    "        return str(dp(2**n-1,k,0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        def dp(n, k, flag):\n",
    "            if(n == 1):\n",
    "                return 0 ^ flag\n",
    "            m = n >> 1\n",
    "            if(k-1 == m):\n",
    "                return 1 ^ flag\n",
    "            elif(k-1 < m):\n",
    "                return dp(m,k,flag)\n",
    "            else:\n",
    "                return dp(m,n-k+1,flag^1)\n",
    "        return str(dp(2**n-1,k,0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        i,a=1,0\n",
    "        while k>i:\n",
    "            i=i<<1\n",
    "        while i!=k:\n",
    "            while i>k:\n",
    "                i=i>>1\n",
    "            if i<k:\n",
    "                k=(i<<1)-k\n",
    "                a=a^1\n",
    "        if k==1:\n",
    "            return str(a)\n",
    "        else:\n",
    "            return str(a^1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        if k == 1:\n",
    "            return \"0\"\n",
    "        n -= 1\n",
    "        mid = 1 << n\n",
    "        if k == mid:\n",
    "            return \"1\"\n",
    "        elif k < mid:\n",
    "            return self.findKthBit(n, k)\n",
    "        else:\n",
    "            k = (mid << 1) - k\n",
    "            return str(1 - int(self.findKthBit(n, k)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        if k == 1:\n",
    "            return \"0\"\n",
    "        \n",
    "        mid = 1 << (n - 1)\n",
    "        if k == mid:\n",
    "            return \"1\"\n",
    "        elif k < mid:\n",
    "            return self.findKthBit(n - 1, k)\n",
    "        else:\n",
    "            k = (mid << 1) - k\n",
    "            return str(1 - int(self.findKthBit(n - 1, k)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        if k == 1:\n",
    "            return \"0\"\n",
    "        n -= 1\n",
    "        mid = 1 << (n)\n",
    "        if k == mid:\n",
    "            return \"1\"\n",
    "        elif k < mid:\n",
    "            return self.findKthBit(n, k)\n",
    "        else:\n",
    "            k = (mid << 1) - k\n",
    "            return str(1 - int(self.findKthBit(n, k)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        if n == 1:\n",
    "            return \"0\"\n",
    "        if n == 2:\n",
    "            return \"011\"[k-1]\n",
    "        \n",
    "        length = 2**n - 1\n",
    "        if k == length//2+1:\n",
    "            return \"1\"\n",
    "        if k < length//2+1:\n",
    "            return self.findKthBit(n-1, k)\n",
    "        k -= (length//2+1)\n",
    "        k = length // 2 + 1 - k\n",
    "        ans = self.findKthBit(n-1, k)\n",
    "        return \"1\" if ans == \"0\" else \"0\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        if k == 1:\n",
    "            return \"0\"\n",
    "        \n",
    "        mid = 1 << (n - 1)\n",
    "        if k == mid:\n",
    "            return \"1\"\n",
    "        elif k < mid:\n",
    "            return self.findKthBit(n - 1, k)\n",
    "        else:\n",
    "            k = mid * 2 - k\n",
    "            return \"0\" if self.findKthBit(n - 1, k) == \"1\" else \"1\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invert(self,s):\n",
    "        return \"1\" if s==\"0\" else \"0\"\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        x=2**(n-1)\n",
    "        if n==1:return \"0\"\n",
    "        if k==x:return \"1\"\n",
    "        if k>x:\n",
    "            return self.invert(self.findKthBit(n-1,x-k%x))\n",
    "        else:\n",
    "            return self.findKthBit(n-1,k)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        if k == 1:\n",
    "            return \"0\"\n",
    "        mid = 1 << (n - 1)\n",
    "        if k == mid:\n",
    "            return \"1\"\n",
    "        elif k < mid:\n",
    "            return self.findKthBit(n - 1, k)\n",
    "        else:\n",
    "            k = mid * 2 - k \n",
    "            return \"0\" if self.findKthBit(n - 1, k) == \"1\" else \"1\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        if n == 1:\n",
    "            return \"0\"\n",
    "        mid = 1 << (n - 1)\n",
    "        if k == mid:\n",
    "            return \"1\"\n",
    "        elif k < mid:\n",
    "            return self.findKthBit(n - 1, k)\n",
    "        else:\n",
    "            k = mid * 2 - k\n",
    "            return \"0\" if self.findKthBit(n - 1, k) == \"1\" else \"1\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        if n == k == 1:\n",
    "            return '0'\n",
    "        \n",
    "        s = 1\n",
    "        for i in range(1,n):\n",
    "            s = (s*2) +1\n",
    "        #print(s)\n",
    "        medium = s // 2 + 1\n",
    "        if k == medium:\n",
    "            return '1'\n",
    "        elif k < medium:\n",
    "            return self.findKthBit(n-1, k)\n",
    "        else:\n",
    "            str1 = self.findKthBit(n-1,2*medium-k)\n",
    "            num = abs(1-int(str1))\n",
    "            return str(num)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        def solve(n, k):\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            \n",
    "            mid = (1 << (n - 1))\n",
    "            if k > mid:\n",
    "                return 1 - solve(n - 1, (1 << n) - k)\n",
    "            elif k < mid:\n",
    "                return solve(n - 1, k)\n",
    "            else:\n",
    "                return 1\n",
    "        \n",
    "        return '1' if solve(n, k) else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "\n",
    "        def getAllNum(n):\n",
    "            dp = [0] * (n+1)\n",
    "            for i in range(1,n+1):\n",
    "                dp[i] = 1+ dp[i-1]*2\n",
    "            return dp\n",
    "        dp = getAllNum(n)\n",
    "\n",
    "        def findKthBit1(n,k):\n",
    "            if n == 1:\n",
    "                return '0'\n",
    "            mid = (dp[n] + 1)//2\n",
    "            if k == mid:\n",
    "                return '1'\n",
    "            elif k<mid:\n",
    "                return findKthBit1(n-1,k)\n",
    "            else:\n",
    "                k = 2*mid - k #离mid偏移k-mid，由于是反向,则取n-1 末尾偏移,mid-(k-mid)\n",
    "                c = findKthBit1(n-1,k)\n",
    "                return '0' if c=='1' else '1'\n",
    "        return findKthBit1(n,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(n, k):\n",
    "        if n==1:\n",
    "            return 0\n",
    "        t=2**(n-1)\n",
    "        if k==t:\n",
    "            return 1\n",
    "        if k<t:\n",
    "            return f(n-1,k)\n",
    "        return 1 - f(n-1,2*t-k)\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        return str(f(n, k))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        if n==1: return '0'\n",
    "        n -= 1\n",
    "        jd = 2**n\n",
    "        if k<jd: return self.findKthBit(n,k)\n",
    "        elif k>jd: return '1' if self.findKthBit(n,jd*2-k)=='0' else '0'\n",
    "        return '1'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 递归\n",
    "    def findKthBit1(self, n: int, k: int) -> str:\n",
    "        if k == 1:\n",
    "            return \"0\"\n",
    "        \n",
    "        mid = 1 << (n - 1)\n",
    "        if k == mid:\n",
    "            return \"1\"\n",
    "        elif k < mid:\n",
    "            return self.findKthBit(n - 1, k)\n",
    "        else:\n",
    "            k = mid * 2 - k\n",
    "            return \"0\" if self.findKthBit(n - 1, k) == \"1\" else \"1\"\n",
    "\n",
    "\n",
    "\n",
    "    # 递归\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        if n == 1 and k == 1:\n",
    "            return '0'\n",
    "\n",
    "        if k == 2**(n - 1):\n",
    "            return '1'\n",
    "\n",
    "        if k < 2**(n - 1):\n",
    "            return self.findKthBit(n - 1, k)\n",
    "\n",
    "        k -= 2**(n - 1)\n",
    "        ans = self.findKthBit(n - 1, 2**(n - 1) - k)\n",
    "        return '1' if ans == '0' else '0'\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        # 返回 reverse(invert(s))\n",
    "        def helper(s):\n",
    "            a = ''\n",
    "            for i in range(len(s)-1, -1, -1):\n",
    "                if s[i] == '0':\n",
    "                    a += '1'\n",
    "                else:\n",
    "                    a += '0'\n",
    "            return a\n",
    "\n",
    "        s = '0'\n",
    "        i = 2\n",
    "        while i <= n:\n",
    "            s += '1' + helper(s)\n",
    "            i += 1\n",
    "        # print(s)\n",
    "        return s[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        # 返回 reverse(invert(s))\n",
    "        def helper(s):\n",
    "            a = ''\n",
    "            for i in range(len(s)-1, -1, -1):\n",
    "                if s[i] == '0':\n",
    "                    a += '1'\n",
    "                else:\n",
    "                    a += '0'\n",
    "            return a\n",
    "\n",
    "        s = '0'\n",
    "        i = 2\n",
    "        while i <= n:\n",
    "            s += '1' + helper(s)\n",
    "            i += 1\n",
    "            # 剪枝\n",
    "            if len(s) >= k:\n",
    "                break\n",
    "        # print(s)\n",
    "        return s[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        # 返回 reverse(invert(s))\n",
    "        def helper(s):\n",
    "            a = ''\n",
    "            for i in range(len(s)-1, -1, -1):\n",
    "                if s[i] == '0':\n",
    "                    a += '1'\n",
    "                else:\n",
    "                    a += '0'\n",
    "            return a\n",
    "\n",
    "        s = '0'\n",
    "        i = 2\n",
    "        while i <= n:\n",
    "            s += '1' + helper(s)\n",
    "            i += 1\n",
    "            if len(s) >= k:\n",
    "                break\n",
    "        # print(s)\n",
    "        return s[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def invert(x):\n",
    "    ans = ''\n",
    "    for xx in x:\n",
    "        if xx == '1':\n",
    "            ans += '0'\n",
    "        else:\n",
    "            ans += '1'\n",
    "    return ans\n",
    "\n",
    "s1 = '0'\n",
    "for _ in range(19):\n",
    "    s1 = s1 + '1' + invert(s1[::-1])\n",
    "# print(s1)\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        #递推规律\n",
    "        return s1[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        def change(n, s):\n",
    "            if n == 1:\n",
    "                return s\n",
    "            \n",
    "            return change(n - 1, s + '1' + bin(2**len(s) - 1 - int(s,2))[2:][::-1])\n",
    "        return change(n,'0')[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        # 返回第i次串联操作的结果, 前一次操作结果为preS\n",
    "        def dfs(i, preS):\n",
    "            if i > n:\n",
    "                return preS\n",
    "\n",
    "            invertS = ''\n",
    "            for c in preS:\n",
    "                if c == '0':\n",
    "                    invertS += '1'\n",
    "                else:\n",
    "                    invertS += '0'\n",
    "            s = preS + '1' + invertS[::-1]\n",
    "            return dfs(i+1, s)\n",
    "\n",
    "        ans = dfs(2, '0')\n",
    "        # print(ans)\n",
    "        return ans[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        def recur(count: int) -> str:\n",
    "            if count == 0:\n",
    "                return \"0\"\n",
    "            s = recur(count - 1)\n",
    "            \n",
    "            ns = \"\"\n",
    "            for i, c in enumerate(s[::-1]):\n",
    "                if c == \"0\":\n",
    "                     ns += \"1\"\n",
    "                else:\n",
    "                    ns += \"0\"\n",
    "            return s + \"1\" + ns\n",
    "        ans = recur(n)\n",
    "        return ans[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        def recur(count: int) -> str:\n",
    "            if count == 0:\n",
    "                return \"0\"\n",
    "            s = recur(count - 1)\n",
    "            \n",
    "            ns = \"\"\n",
    "            for i, c in enumerate(s[::-1]):\n",
    "                if c == \"0\":\n",
    "                     ns += \"1\"\n",
    "                else:\n",
    "                    ns += \"0\"\n",
    "            return s + \"1\" + ns\n",
    "        ans = recur(n)\n",
    "        return ans[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        def reverse(s:str):\n",
    "            return s[::-1]\n",
    "        def invert(s:str):\n",
    "            ans = \"\"\n",
    "            for i in s:\n",
    "                if i == \"0\":\n",
    "                    ans += \"1\"\n",
    "                else :\n",
    "                    ans += \"0\"\n",
    "            return ans\n",
    "        ans = \"0\"\n",
    "        for i in range(1,n+1):\n",
    "            ans += (\"1\" + reverse(invert(ans)))\n",
    "        return ans[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "\n",
    "        def invert(s):\n",
    "            temp= ''\n",
    "            for c in s:\n",
    "                if c == '0':\n",
    "                    temp +='1'\n",
    "                else:\n",
    "                    temp +='0'\n",
    "            return temp\n",
    "\n",
    "\n",
    "        def reverse(s):\n",
    "            s_list = list(s)\n",
    "            n = len(s)\n",
    "            i =0 \n",
    "            j = n -1\n",
    "            while (i < j):\n",
    "                s_list[i],s_list[j] = s_list[j],s_list[i]\n",
    "                i +=1\n",
    "                j -=1\n",
    "            return ''.join(s_list)\n",
    "\n",
    "\n",
    "        def getString(n):\n",
    "            if n == 1:\n",
    "                return '0'\n",
    "            y = getString(n-1)\n",
    "            return y + '1' + reverse(invert(y))\n",
    "        return getString(n)[k-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        if n == 1: return '0'\n",
    "        s = '0'\n",
    "        for i in range(1, n):\n",
    "            temp = ''.join(['1' if i == '0' else '0' for i in s[::-1]])\n",
    "            s += '1' + temp\n",
    "        return s[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        if n == 1: return '0'\n",
    "        s = '0'\n",
    "        for i in range(1, n):\n",
    "            temp = ''.join(['1' if i == '0' else '0' for i in s[::-1]])\n",
    "            s += '1' + temp\n",
    "        return s[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        def invert(s):\n",
    "            res = ''\n",
    "            for i in s:\n",
    "                if i == '0':\n",
    "                    res += '1'\n",
    "                else:\n",
    "                    res += '0'\n",
    "            return res[::-1]\n",
    "        ans = '0'\n",
    "        for i in range(n):\n",
    "            temp = ans + '1' + invert(ans)\n",
    "            ans = temp\n",
    "        return ans[k-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        str = self.build_str(None)\n",
    "        for i in range(n) :\n",
    "            str = self.build_str(str)\n",
    "            pass\n",
    "        return str[k-1]\n",
    "        pass\n",
    "\n",
    "    def build_str(self, prev_str):\n",
    "        if prev_str == None:\n",
    "            return '0'\n",
    "        return prev_str + '1' + self.reverse(prev_str)\n",
    "        pass\n",
    "\n",
    "    def reverse(self, prev_str):\n",
    "        s = ''\n",
    "        for c in prev_str :\n",
    "            if c == '1' :\n",
    "                s += '0'\n",
    "            else:\n",
    "                s += '1'\n",
    "            pass\n",
    "        result = ''\n",
    "        for i in range(len(s)-1,0-1,-1) :\n",
    "            result += s[i]\n",
    "        return result\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        # 模拟 \n",
    "        s = [0]\n",
    "\n",
    "        for _ in range(n-1):\n",
    "            s.append(1)\n",
    "            s.extend(1 - i for i in s[-2::-1])\n",
    "        return str(s[k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "\n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i == 1:\n",
    "                return '0'\n",
    "            if i == 2:\n",
    "                return '011'\n",
    "            s = f(i - 1)\n",
    "            s1 = ''.join('0' if x == '1' else '1' for x in s)\n",
    "            return s + '1' + s1[::-1]\n",
    "        \n",
    "        return f(n)[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        temp  = self.recursion(n)\n",
    "        return temp[k-1]\n",
    "\n",
    "\n",
    "    def reverse(self,s):\n",
    "        i = 0\n",
    "        j = len(s)-1\n",
    "        temp = list(s)\n",
    "        while i < j:\n",
    "            temp[i],temp[j] = temp[j],temp[i]\n",
    "            i +=1\n",
    "            j -=1\n",
    "        return ''.join(temp)\n",
    "\n",
    "\n",
    "\n",
    "    def invert(self,s):\n",
    "        temp = ''\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '0':\n",
    "                temp +='1'\n",
    "            else:\n",
    "                temp +='0'\n",
    "        return temp\n",
    "\n",
    "    def recursion(self,n):\n",
    "        if n ==0:\n",
    "            return '0'\n",
    "        y = self.recursion(n-1)\n",
    "        return str(y) +'1' + self.reverse(self.invert(y))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef findKthBit(self, n: int, k: int) -> str:\n",
    "\t\tdef get_str(n):\n",
    "\t\t\tif n == 0:\n",
    "\t\t\t\treturn '0'\n",
    "\t\t\telse:\n",
    "\t\t\t\ttemp = get_str(n - 1)\n",
    "\t\t\t\treturn temp + '1' + ''.join([chr(97 - ord(ch)) for ch in temp])[::-1]\n",
    "\n",
    "\t\treturn get_str(n)[k - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef findKthBit(self, n: int, k: int) -> str:\n",
    "\t\tdef get_str(n):\n",
    "\t\t\tif n == 0:\n",
    "\t\t\t\treturn '0'\n",
    "\t\t\telse:\n",
    "\t\t\t\ttemp = get_str(n - 1)\n",
    "\t\t\t\treturn temp + '1' + ''.join([chr(97 - ord(ch)) for ch in temp])[::-1]\n",
    "\n",
    "\t\treturn get_str(n)[k - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef findKthBit(self, n: int, k: int) -> str:\n",
    "\t\tdef get_str(n):\n",
    "\t\t\tif n == 0:\n",
    "\t\t\t\treturn '0'\n",
    "\t\t\telse:\n",
    "\t\t\t\ttemp = get_str(n - 1)\n",
    "\t\t\t\treturn temp + '1' + ''.join(['1' if ch == '0' else '0' for ch in temp])[::-1]\n",
    "\n",
    "\t\treturn get_str(n)[k - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef findKthBit(self, n: int, k: int) -> str:\n",
    "\t\tdef get_str(n):\n",
    "\t\t\tif n == 0:\n",
    "\t\t\t\treturn '0'\n",
    "\t\t\telse:\n",
    "\t\t\t\ttemp = get_str(n - 1)\n",
    "\t\t\t\treturn temp + '1' + ''.join(['1' if ch == '0' else '0' for ch in temp])[::-1]\n",
    "\n",
    "\t\treturn get_str(n)[k - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        s = [0]\n",
    "        for _ in range(n-1):\n",
    "            s = s + [1] + [i^1 for i in s[::-1]]\n",
    "        return str(s[k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dp = ['0'] * 20\n",
    "def reverse(s):\n",
    "    n = len(s)\n",
    "    s = list(s)\n",
    "    s = s[::-1]\n",
    "    for i in range(n):\n",
    "        s[i] = str(1 - int(s[i]))\n",
    "    return ''.join(s)\n",
    "for i in range(1, 20):\n",
    "    dp[i] = dp[i - 1] + '1' + reverse(dp[i - 1])\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        return dp[-1][k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        \n",
    "        s = \"0\"\n",
    "        \n",
    "        def get(num):\n",
    "            \n",
    "            t = list(num)\n",
    "            for i in range(len(t)):\n",
    "                t[i] = str(int(t[i]) ^ 1)\n",
    "            \n",
    "            return ''.join(t)[::-1]\n",
    "        \n",
    "        for i in range(n - 1):\n",
    "            s = s + '1' + get(s)\n",
    "        \n",
    "        \n",
    "        return s[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dp = [\"\", \"0\"]\n",
    "for x in range(2, 21):\n",
    "    dp.append(dp[-1]+\"1\"+\"\".join([str(1-int(w)) for w in dp[-1]])[::-1])\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        return dp[n][k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        # 模拟 \n",
    "        s = '0'\n",
    "        def invert(s):\n",
    "            return ''.join(str(1 - int(c)) for c in s)\n",
    "\n",
    "        for _ in range(n-1):\n",
    "            s = s + '1' + invert(s)[::-1]\n",
    "        return s[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        s = '0'\n",
    "        while n > 1:\n",
    "            t = [str(int(x) ^ 1) for x in s]\n",
    "            t = ''.join(t)\n",
    "            s = s + '1' + t[::-1]\n",
    "            n -= 1\n",
    "\n",
    "        return s[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        # 模拟 \n",
    "        s = '0'\n",
    "\n",
    "        for _ in range(n-1):\n",
    "            s = s + '1' + ''.join(str(1 - int(c)) for c in s[::-1])\n",
    "        return s[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthBit(self, n: int, k: int) -> str:\n",
    "        dp = ['0'] * n\n",
    "        def reverse(s):\n",
    "            n = len(s)\n",
    "            s = list(s)\n",
    "            s = s[::-1]\n",
    "            for i in range(n):\n",
    "                s[i] = str(1 - int(s[i]))\n",
    "            return ''.join(s)\n",
    "        for i in range(1, n):\n",
    "            dp[i] = dp[i - 1] + '1' + reverse(dp[i - 1])\n",
    "        return dp[-1][k - 1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
